package org.example.datastructure;

import java.util.ArrayList;
import java.util.List;

/**
 * @author juntao zhang
 */
public class Test {
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }

        int max = Integer.MIN_VALUE;
        int sum = 0;

        int len = A.length;
        for (int i = 0; i < len; i++) {
            if (sum < 0) {
                sum = 0;
            }

            sum += A[i];
            max = Math.max(max, sum);
        }

        return max;
    }

    public double maxAverage(int[] nums, int k) {
        // Write your code here
        double l = Integer.MAX_VALUE, r = Integer.MIN_VALUE;
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] < l)
                l = nums[i];
            if (nums[i] > r)
                r = nums[i];
        }

        double[] sum = new double[n + 1];
        sum[0] = 0;
        while (r - l >= 1e-6) {
            double mid = (l + r) / 2.0;

            double min_pre = 0;
            boolean check = false;
            for (int i = 1; i <= n; ++i) {
                sum[i] = sum[i - 1] + nums[i - 1] - mid;
                if (i >= k && sum[i] - min_pre >= 0) {
                    check = true;
                    break;
                }
                if (i >= k)
                    min_pre = Math.min(min_pre, sum[i - k + 1]);
            }
            if (check)
                l = mid;
            else
                r = mid;
            System.out.println("l=" + l + ";r=" + r);
        }

        return l;
    }

    public static void main(String[] args) {
//        System.out.println(new Test().maxSubArray(new int[]{-2, -1}));
        System.out.println(new Test().maxAverage(new int[]{1, 12, -5, -6, 50, 3}, 3));
    }
}
